package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.ListNode;

import java.util.Locale;

/**
 * 反转链表
 *
 * @author yuhushuan
 * @date 2020/6/18 10:54
 */
public class _24_1_ReverseList {
    private static ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode current = head;

        while (current.getNext() != null) {
            ListNode nextNode = current.getNext();
            // 断开下一个节点
            current.setNext(nextNode.getNext());
            // 下一节点指向头节点
            nextNode.setNext(head);
            // 头节点为断开节点
            head = nextNode;
        }
        return head;
    }

    /**
     * 递归实现
     *
     * @param node
     * @return
     */
    private static ListNode reverseList_Recursively(ListNode node) {
        if (node == null) {
            return null;
        }
        if (node.getNext() == null) {
            return node;
        }
        // 得到当前节点的下一节点
        ListNode nextNode = node.getNext();
        // 打断当前节点
        node.setNext(null);
        // 每次递归下一节点进行反转
        ListNode pre = reverseList_Recursively(nextNode);
        nextNode.setNext(node);
        return pre;
    }

    public static void main(String[] args) {
        print(null);
        print(new ListNode(1));

        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 10; i++) {
            ListNode next = new ListNode(i);
            node.setNext(next);
            node = next;
        }
        print(head);
    }

    private static void print(ListNode head) {
        System.out.println(String.format(Locale.getDefault(),
                "链表遍历：\n%s", head));
        System.out.println("反转链表-指针：");
        System.out.println(head = reverseList(head));
        System.out.println("反转链表-递归：");
        System.out.println(reverseList_Recursively(head));
        System.out.println();
    }

}
